<?xml version="1.0" encoding="ascii"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
          "DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
  <title>graph.classes.Digraph.digraph</title>
  <link rel="stylesheet" href="epydoc.css" type="text/css" />
  <script type="text/javascript" src="epydoc.js"></script>
</head>

<body bgcolor="white" text="black" link="blue" vlink="#204080"
      alink="#204080">
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="graph-module.html">Home</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Project homepage -->
      <th class="navbar" align="right" width="100%">
        <table border="0" cellpadding="0" cellspacing="0">
          <tr><th class="navbar" align="center"
            ><a class="navbar" target="_top" href="http://code.google.com/p/python-graph/">python-graph</a></th>
          </tr></table></th>
  </tr>
</table>
<table width="100%" cellpadding="0" cellspacing="0">
  <tr valign="top">
    <td width="100%">
      <span class="breadcrumbs">
        <a href="graph-module.html">Package&nbsp;graph</a> ::
        <a href="graph.classes-module.html">Package&nbsp;classes</a> ::
        <a href="graph.classes.Digraph-module.html">Module&nbsp;Digraph</a> ::
        Class&nbsp;digraph
      </span>
    </td>
    <td>
      <table cellpadding="0" cellspacing="0">
        <!-- hide/show private -->
      </table>
    </td>
  </tr>
</table>
<!-- ==================== CLASS DESCRIPTION ==================== -->
<h1 class="epydoc">Class digraph</h1><p class="nomargin-top"></p>
<pre class="base-tree">
object --+
         |
        <strong class="uidshort">digraph</strong>
</pre>

<hr />
<p>Digraph class.</p>
  <p>Digraphs are built of nodes and directed edges.</p>

<!-- ==================== INSTANCE METHODS ==================== -->
<a name="section-InstanceMethods"></a>
<table class="summary" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td align="left" colspan="2" class="table-header">
    <span class="table-header">Instance Methods</span></td>
</tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#__init__" class="summary-sig-name">__init__</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Initialize a digraph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">iterator</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#__getitem__" class="summary-sig-name">__getitem__</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>)</span><br />
      Return a iterator passing through all neighbors of the given node.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">iterator</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#__iter__" class="summary-sig-name">__iter__</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return a iterator passing through all nodes in the digraph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">number</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#__len__" class="summary-sig-name">__len__</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return the order of the digraph when requested by len().</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">string</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#__str__" class="summary-sig-name">__str__</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return a string representing the digraph when requested by str() (or 
      print).</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#add_edge" class="summary-sig-name">add_edge</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>,
        <span class="summary-sig-arg">wt</span>=<span class="summary-sig-default">1</span>,
        <span class="summary-sig-arg">label</span>=<span class="summary-sig-default"><code class="variable-quote">'</code><code class="variable-string"></code><code class="variable-quote">'</code></span>,
        <span class="summary-sig-arg">attrs</span>=<span class="summary-sig-default"><code class="variable-group">[</code><code class="variable-group">]</code></span>)</span><br />
      Add an directed edge (u,v) to the graph connecting nodes u to v.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#add_edge_attribute" class="summary-sig-name">add_edge_attribute</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>,
        <span class="summary-sig-arg">attr</span>)</span><br />
      Add attribute to the given edge.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#add_graph" class="summary-sig-name">add_graph</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">graph</span>)</span><br />
      Add other graph to the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#add_node" class="summary-sig-name">add_node</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>,
        <span class="summary-sig-arg">attrs</span>=<span class="summary-sig-default"><code class="variable-group">[</code><code class="variable-group">]</code></span>)</span><br />
      Add given node to the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#add_node_attribute" class="summary-sig-name">add_node_attribute</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>,
        <span class="summary-sig-arg">attr</span>)</span><br />
      Add attribute to the given node.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#add_nodes" class="summary-sig-name">add_nodes</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">nodelist</span>)</span><br />
      Add given nodes to the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#add_spanning_tree" class="summary-sig-name">add_spanning_tree</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">st</span>)</span><br />
      Add a spanning tree to the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#complete" class="summary-sig-name">complete</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Make the graph a complete graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">List</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#critical_path" class="summary-sig-name">critical_path</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Compute and return the critical path in an acyclic directed weighted 
      graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">number</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#degree" class="summary-sig-name">degree</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>)</span><br />
      Return the degree of the given node.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#del_edge" class="summary-sig-name">del_edge</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>)</span><br />
      Remove an directed edge (u, v) from the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#del_node" class="summary-sig-name">del_node</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>)</span><br />
      Remove a node from the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#edges" class="summary-sig-name">edges</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return all edges in the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#get_edge_attributes" class="summary-sig-name">get_edge_attributes</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>)</span><br />
      Return the attributes of the given edge.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">string</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#get_edge_label" class="summary-sig-name">get_edge_label</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>)</span><br />
      Get the label of an edge.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">number</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#get_edge_weight" class="summary-sig-name">get_edge_weight</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>)</span><br />
      Get the weight of an edge.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#get_node_attributes" class="summary-sig-name">get_node_attributes</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>)</span><br />
      Return the attributes of the given node.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">boolean</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#has_edge" class="summary-sig-name">has_edge</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>)</span><br />
      Return whether an edge between nodes u and v exists.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">boolean</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#has_node" class="summary-sig-name">has_node</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>)</span><br />
      Return whether the requested node exists.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#incidents" class="summary-sig-name">incidents</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>)</span><br />
      Return all nodes that are incident to the given node.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">graph</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#inverse" class="summary-sig-name">inverse</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return the inverse of the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#neighbors" class="summary-sig-name">neighbors</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>)</span><br />
      Return all nodes that are directly accessible from given node.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#nodes" class="summary-sig-name">nodes</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return node list.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">number</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#order" class="summary-sig-name">order</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>)</span><br />
      Return the order of the given node.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#set_edge_label" class="summary-sig-name">set_edge_label</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>,
        <span class="summary-sig-arg">label</span>)</span><br />
      Set the label of an edge.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#set_edge_weight" class="summary-sig-name">set_edge_weight</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">u</span>,
        <span class="summary-sig-arg">v</span>,
        <span class="summary-sig-arg">wt</span>)</span><br />
      Set the weight of an edge.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">List</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#transitive_edges" class="summary-sig-name">transitive_edges</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return a list of transitive edges.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">iterator</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#traversal" class="summary-sig-name">traversal</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">node</span>,
        <span class="summary-sig-arg">order</span>=<span class="summary-sig-default"><code class="variable-quote">'</code><code class="variable-string">pre</code><code class="variable-quote">'</code></span>)</span><br />
      Graph traversal iterator.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#generate" class="summary-sig-name">generate</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">num_nodes</span>,
        <span class="summary-sig-arg">num_edges</span>,
        <span class="summary-sig-arg">weight_range</span>=<span class="summary-sig-default"><code class="variable-group">(</code>1<code class="variable-op">, </code>1<code class="variable-group">)</code></span>)</span><br />
      Add nodes and random edges to the graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">&nbsp;</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#read" class="summary-sig-name">read</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">string</span>,
        <span class="summary-sig-arg">fmt</span>=<span class="summary-sig-default"><code class="variable-quote">'</code><code class="variable-string">xml</code><code class="variable-quote">'</code></span>)</span><br />
      Read a graph from a string.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">string</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#write" class="summary-sig-name">write</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">fmt</span>=<span class="summary-sig-default"><code class="variable-quote">'</code><code class="variable-string">xml</code><code class="variable-quote">'</code></span>)</span><br />
      Write the graph to a string.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">dictionary</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#accessibility" class="summary-sig-name">accessibility</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Accessibility matrix (transitive closure).</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">dictionary</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#breadth_first_search" class="summary-sig-name">breadth_first_search</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">root</span>=<span class="summary-sig-default">None</span>,
        <span class="summary-sig-arg">filter</span>=<span class="summary-sig-default">filters.null()</span>)</span><br />
      Breadth-first search.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#cut_edges" class="summary-sig-name">cut_edges</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return the cut-edges of the given graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#cut_nodes" class="summary-sig-name">cut_nodes</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Return the cut-nodes of the given graph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">tuple</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#depth_first_search" class="summary-sig-name">depth_first_search</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">root</span>=<span class="summary-sig-default">None</span>,
        <span class="summary-sig-arg">filter</span>=<span class="summary-sig-default">filters.null()</span>)</span><br />
      Depht-first search.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#heuristic_search" class="summary-sig-name">heuristic_search</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">start</span>,
        <span class="summary-sig-arg">goal</span>,
        <span class="summary-sig-arg">heuristic</span>)</span><br />
      A* search algorithm.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#mutual_accessibility" class="summary-sig-name">mutual_accessibility</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Mutual-accessibility matrix (strongly connected components).</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">tuple</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#shortest_path" class="summary-sig-name">shortest_path</a>(<span class="summary-sig-arg">self</span>,
        <span class="summary-sig-arg">source</span>)</span><br />
      Return the shortest path distance between source node and all other 
      nodes using Dijkstra's algorithm.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#topological_sorting" class="summary-sig-name">topological_sorting</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Topological sorting.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
<tr>
    <td width="15%" align="right" valign="top" class="summary">
      <span class="summary-type">list</span>
    </td><td class="summary">
      <table width="100%" cellpadding="0" cellspacing="0" border="0">
        <tr>
          <td><span class="summary-sig"><a href="graph.classes.Digraph.digraph-class.html#find_cycle" class="summary-sig-name">find_cycle</a>(<span class="summary-sig-arg">self</span>)</span><br />
      Find a cycle in the digraph.</td>
          <td align="right" valign="top">
            
            
          </td>
        </tr>
      </table>
      
    </td>
  </tr>
  <tr>
    <td colspan="2" class="summary">
    <p class="indent-wrapped-lines"><b>Inherited from <code>object</code></b>:
      <code>__delattr__</code>,
      <code>__getattribute__</code>,
      <code>__hash__</code>,
      <code>__new__</code>,
      <code>__reduce__</code>,
      <code>__reduce_ex__</code>,
      <code>__repr__</code>,
      <code>__setattr__</code>
      </p>
    </td>
  </tr>
</table>
<!-- ==================== PROPERTIES ==================== -->
<a name="section-Properties"></a>
<table class="summary" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td align="left" colspan="2" class="table-header">
    <span class="table-header">Properties</span></td>
</tr>
  <tr>
    <td colspan="2" class="summary">
    <p class="indent-wrapped-lines"><b>Inherited from <code>object</code></b>:
      <code>__class__</code>
      </p>
    </td>
  </tr>
</table>
<!-- ==================== METHOD DETAILS ==================== -->
<a name="section-MethodDetails"></a>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr bgcolor="#70b0f0" class="table-header">
  <td align="left" colspan="2" class="table-header">
    <span class="table-header">Method Details</span></td>
</tr>
</table>
<a name="__init__"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">__init__</span>(<span class="sig-arg">self</span>)</span>
    <br /><em class="fname">(Constructor)</em>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Initialize a digraph.</p>
  <dl class="fields">
    <dt>Overrides:
        object.__init__
    </dt>
  </dl>
</td></tr></table>
</div>
<a name="__getitem__"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">__getitem__</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>)</span>
    <br /><em class="fname">(Indexing operator)</em>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return a iterator passing through all neighbors of the given node.</p>
  <dl class="fields">
    <dt>Returns: iterator</dt>
        <dd>Iterator passing through all neighbors of the given node.</dd>
  </dl>
</td></tr></table>
</div>
<a name="__iter__"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">__iter__</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return a iterator passing through all nodes in the digraph.</p>
  <dl class="fields">
    <dt>Returns: iterator</dt>
        <dd>Iterator passing through all nodes in the digraph.</dd>
  </dl>
</td></tr></table>
</div>
<a name="__len__"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">__len__</span>(<span class="sig-arg">self</span>)</span>
    <br /><em class="fname">(Length operator)</em>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the order of the digraph when requested by len().</p>
  <dl class="fields">
    <dt>Returns: number</dt>
        <dd>Size of the graph.</dd>
  </dl>
</td></tr></table>
</div>
<a name="__str__"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">__str__</span>(<span class="sig-arg">self</span>)</span>
    <br /><em class="fname">(Informal representation operator)</em>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return a string representing the digraph when requested by str() (or 
  print).</p>
  <dl class="fields">
    <dt>Returns: string</dt>
        <dd>String representing the graph.</dd>
    <dt>Overrides:
        object.__str__
    </dt>
  </dl>
</td></tr></table>
</div>
<a name="add_edge"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">add_edge</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>,
        <span class="sig-arg">wt</span>=<span class="sig-default">1</span>,
        <span class="sig-arg">label</span>=<span class="sig-default"><code class="variable-quote">'</code><code class="variable-string"></code><code class="variable-quote">'</code></span>,
        <span class="sig-arg">attrs</span>=<span class="sig-default"><code class="variable-group">[</code><code class="variable-group">]</code></span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Add an directed edge (u,v) to the graph connecting nodes u to v.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
        <li><strong class="pname"><code>wt</code></strong> (number) - Edge weight.</li>
        <li><strong class="pname"><code>label</code></strong> (string) - Edge label.</li>
        <li><strong class="pname"><code>attrs</code></strong> (list) - List of node attributes specified as (attribute, value) tuples.</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="add_edge_attribute"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">add_edge_attribute</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>,
        <span class="sig-arg">attr</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Add attribute to the given edge.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
        <li><strong class="pname"><code>attr</code></strong> (tuple) - Node attribute specified as a tuple in the form (attribute, 
          value).</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="add_graph"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">add_graph</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">graph</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Add other graph to the graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>graph</code></strong> (graph) - Graph</li>
    </ul></dd>
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        Attributes and labels are not preserved.
      </p>
</div></td></tr></table>
</div>
<a name="add_node"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">add_node</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>,
        <span class="sig-arg">attrs</span>=<span class="sig-default"><code class="variable-group">[</code><code class="variable-group">]</code></span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Add given node to the graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>node</code></strong> (node) - Node identifier.</li>
        <li><strong class="pname"><code>attrs</code></strong> (list) - List of node attributes specified as (attribute, value) tuples.</li>
    </ul></dd>
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        While nodes can be of any type, it's strongly recommended to use 
        only numbers and single-line strings as node identifiers if you 
        intend to use write().
      </p>
</div></td></tr></table>
</div>
<a name="add_node_attribute"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">add_node_attribute</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>,
        <span class="sig-arg">attr</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Add attribute to the given node.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li>
        <li><strong class="pname"><code>attr</code></strong> (tuple) - Node attribute specified as a tuple in the form (attribute, 
          value).</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="add_nodes"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">add_nodes</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">nodelist</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Add given nodes to the graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>nodelist</code></strong> (list) - List of nodes to be added to the graph.</li>
    </ul></dd>
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        While nodes can be of any type, it's strongly recommended to use 
        only numbers and single-line strings as node identifiers if you 
        intend to use write().
      </p>
</div></td></tr></table>
</div>
<a name="add_spanning_tree"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">add_spanning_tree</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">st</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Add a spanning tree to the graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>st</code></strong> (dictionary) - Spanning tree.</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="complete"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">complete</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Make the graph a complete graph.</p>
  <dl class="fields">
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        This will modify the current graph.
      </p>
</div></td></tr></table>
</div>
<a name="critical_path"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">critical_path</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Compute and return the critical path in an acyclic directed weighted 
  graph.</p>
  <dl class="fields">
    <dt>Returns: List</dt>
        <dd>List containing all the nodes in the path (or an empty array if 
          the graph contains a cycle)</dd>
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        this function is only meaningful for directed weighted acyclic 
        graphs
      </p>
</div></td></tr></table>
</div>
<a name="degree"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">degree</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the degree of the given node.</p>
  <dl class="fields">
    <dt>Returns: number</dt>
        <dd>Order of the given node.</dd>
  </dl>
</td></tr></table>
</div>
<a name="del_edge"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">del_edge</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Remove an directed edge (u, v) from the graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="del_node"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">del_node</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Remove a node from the graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>node</code></strong> (node) - Node identifier.</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="edges"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">edges</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return all edges in the graph.</p>
  <dl class="fields">
    <dt>Returns: list</dt>
        <dd>List of all edges in the graph.</dd>
  </dl>
</td></tr></table>
</div>
<a name="get_edge_attributes"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">get_edge_attributes</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the attributes of the given edge.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
    </ul></dd>
    <dt>Returns: list</dt>
        <dd>List of attributes specified tuples in the form (attribute, 
          value).</dd>
  </dl>
</td></tr></table>
</div>
<a name="get_edge_label"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">get_edge_label</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Get the label of an edge.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
    </ul></dd>
    <dt>Returns: string</dt>
        <dd>Edge label</dd>
  </dl>
</td></tr></table>
</div>
<a name="get_edge_weight"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">get_edge_weight</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Get the weight of an edge.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
    </ul></dd>
    <dt>Returns: number</dt>
        <dd>Edge weight.</dd>
  </dl>
</td></tr></table>
</div>
<a name="get_node_attributes"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">get_node_attributes</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the attributes of the given node.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li>
    </ul></dd>
    <dt>Returns: list</dt>
        <dd>List of attributes specified tuples in the form (attribute, 
          value).</dd>
  </dl>
</td></tr></table>
</div>
<a name="has_edge"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">has_edge</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return whether an edge between nodes u and v exists.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
    </ul></dd>
    <dt>Returns: boolean</dt>
        <dd>Truth-value for edge existence.</dd>
  </dl>
</td></tr></table>
</div>
<a name="has_node"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">has_node</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return whether the requested node exists.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li>
    </ul></dd>
    <dt>Returns: boolean</dt>
        <dd>Truth-value for node existence.</dd>
  </dl>
</td></tr></table>
</div>
<a name="incidents"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">incidents</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return all nodes that are incident to the given node.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li>
    </ul></dd>
    <dt>Returns: list</dt>
        <dd>List of nodes directly accessible from given node.</dd>
  </dl>
</td></tr></table>
</div>
<a name="inverse"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">inverse</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the inverse of the graph.</p>
  <dl class="fields">
    <dt>Returns: graph</dt>
        <dd>Complement graph for the graph.</dd>
  </dl>
</td></tr></table>
</div>
<a name="neighbors"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">neighbors</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return all nodes that are directly accessible from given node.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>node</code></strong> (node) - Node identifier</li>
    </ul></dd>
    <dt>Returns: list</dt>
        <dd>List of nodes directly accessible from given node.</dd>
  </dl>
</td></tr></table>
</div>
<a name="nodes"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">nodes</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return node list.</p>
  <dl class="fields">
    <dt>Returns: list</dt>
        <dd>Node list.</dd>
  </dl>
</td></tr></table>
</div>
<a name="order"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">order</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the order of the given node.</p>
  <dl class="fields">
    <dt>Returns: number</dt>
        <dd>Order of the given node.</dd>
  </dl>
</td></tr></table>
</div>
<a name="set_edge_label"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">set_edge_label</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>,
        <span class="sig-arg">label</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Set the label of an edge.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
        <li><strong class="pname"><code>label</code></strong> (string) - Edge label.</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="set_edge_weight"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">set_edge_weight</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">u</span>,
        <span class="sig-arg">v</span>,
        <span class="sig-arg">wt</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Set the weight of an edge.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>u</code></strong> (node) - One node.</li>
        <li><strong class="pname"><code>v</code></strong> (node) - Other node.</li>
        <li><strong class="pname"><code>wt</code></strong> (number) - Edge weight.</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="transitive_edges"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">transitive_edges</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return a list of transitive edges.</p>
  <p>Example of transitivity within graphs: A -&gt; B, B -&gt; C, A -&gt;  
  C in this case the transitive edge is: A -&gt; C</p>
  <dl class="fields">
    <dt>Returns: List</dt>
        <dd>List containing tuples with transitive edges (or an empty array 
          if the digraph contains a cycle)</dd>
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        this function is only meaningful for directed acyclic graphs
      </p>
</div></td></tr></table>
</div>
<a name="traversal"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">traversal</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">node</span>,
        <span class="sig-arg">order</span>=<span class="sig-default"><code class="variable-quote">'</code><code class="variable-string">pre</code><code class="variable-quote">'</code></span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Graph traversal iterator.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>node</code></strong> (node) - Node.</li>
        <li><strong class="pname"><code>order</code></strong> (string) - traversal ordering. Possible values are:
          <ol start="2">
            <li>
              'pre' - Preordering (default)
            </li>
          </ol>
          <ol start="1">
            <li>
              'post' - Postordering
            </li>
          </ol></li>
    </ul></dd>
    <dt>Returns: iterator</dt>
        <dd>Traversal iterator.</dd>
  </dl>
</td></tr></table>
</div>
<a name="generate"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">generate</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">num_nodes</span>,
        <span class="sig-arg">num_edges</span>,
        <span class="sig-arg">weight_range</span>=<span class="sig-default"><code class="variable-group">(</code>1<code class="variable-op">, </code>1<code class="variable-group">)</code></span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Add nodes and random edges to the graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>num_nodes</code></strong> (number) - Number of nodes.</li>
        <li><strong class="pname"><code>num_edges</code></strong> (number) - Number of edges.</li>
        <li><strong class="pname"><code>weight_range</code></strong> (tuple) - tuple of two integers as lower and upper limits on randomly 
          generated weights (uniform distribution).</li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="read"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">read</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">string</span>,
        <span class="sig-arg">fmt</span>=<span class="sig-default"><code class="variable-quote">'</code><code class="variable-string">xml</code><code class="variable-quote">'</code></span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Read a graph from a string. Nodes and edges specified in the input 
  will be added to the current graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>string</code></strong> (string) - Input string specifying a graph.</li>
        <li><strong class="pname"><code>fmt</code></strong> (string) - Input format. Possible formats are:
          <ol start="1">
            <li>
              'xml' - XML (default)
            </li>
            <li>
              'dot' - DOT Language
            </li>
          </ol></li>
    </ul></dd>
  </dl>
</td></tr></table>
</div>
<a name="write"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">write</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">fmt</span>=<span class="sig-default"><code class="variable-quote">'</code><code class="variable-string">xml</code><code class="variable-quote">'</code></span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Write the graph to a string. Depending of the output format, this 
  string can be used by read() to rebuild the graph.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>fmt</code></strong> (string) - Output format. Possible formats are:
          <ol start="1">
            <li>
              'xml' - XML (default)
            </li>
            <li>
              'dot' - DOT Language (for GraphViz)
            </li>
            <li>
              'dotwt' - DOT Language with edge weight information
            </li>
          </ol></li>
    </ul></dd>
    <dt>Returns: string</dt>
        <dd>String specifying the graph.</dd>
  </dl>
</td></tr></table>
</div>
<a name="accessibility"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">accessibility</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Accessibility matrix (transitive closure).</p>
  <dl class="fields">
    <dt>Returns: dictionary</dt>
        <dd>Accessibility information for each node.</dd>
  </dl>
</td></tr></table>
</div>
<a name="breadth_first_search"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">breadth_first_search</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">root</span>=<span class="sig-default">None</span>,
        <span class="sig-arg">filter</span>=<span class="sig-default">filters.null()</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Breadth-first search.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>root</code></strong> (node) - Optional root node (will explore only root's connected component)</li>
    </ul></dd>
    <dt>Returns: dictionary</dt>
        <dd>A tuple containing a dictionary and a list.
          <ol start="1">
            <li>
              Generated spanning tree
            </li>
            <li>
              Graph's level-based ordering
            </li>
          </ol></dd>
  </dl>
</td></tr></table>
</div>
<a name="cut_edges"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">cut_edges</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the cut-edges of the given graph.</p>
  <dl class="fields">
    <dt>Returns: list</dt>
        <dd>List of cut-edges.</dd>
  </dl>
</td></tr></table>
</div>
<a name="cut_nodes"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">cut_nodes</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the cut-nodes of the given graph.</p>
  <dl class="fields">
    <dt>Returns: list</dt>
        <dd>List of cut-nodes.</dd>
  </dl>
</td></tr></table>
</div>
<a name="depth_first_search"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">depth_first_search</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">root</span>=<span class="sig-default">None</span>,
        <span class="sig-arg">filter</span>=<span class="sig-default">filters.null()</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Depht-first search.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>root</code></strong> (node) - Optional root node (will explore only root's connected component)</li>
    </ul></dd>
    <dt>Returns: tuple</dt>
        <dd>tupple containing a dictionary and two lists:
          <ol start="1">
            <li>
              Generated spanning tree
            </li>
            <li>
              Graph's preordering
            </li>
            <li>
              Graph's postordering
            </li>
          </ol></dd>
  </dl>
</td></tr></table>
</div>
<a name="heuristic_search"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">heuristic_search</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">start</span>,
        <span class="sig-arg">goal</span>,
        <span class="sig-arg">heuristic</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>A* search algorithm.</p>
  <p>A set of heuristics is available under <code>graph.heuristics</code>. 
  User-created heuristics are allowed too.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>start</code></strong> (node) - Start node</li>
        <li><strong class="pname"><code>goal</code></strong> (node) - Goal node</li>
        <li><strong class="pname"><code>heuristic</code></strong> (function) - Heuristic function</li>
    </ul></dd>
    <dt>Returns: list</dt>
        <dd>Optimized path from start to goal node</dd>
  </dl>
</td></tr></table>
</div>
<a name="mutual_accessibility"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">mutual_accessibility</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Mutual-accessibility matrix (strongly connected components).</p>
  <dl class="fields">
    <dt>Returns: list</dt>
        <dd>Mutual-accessibility information for each node.</dd>
  </dl>
</td></tr></table>
</div>
<a name="shortest_path"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">shortest_path</span>(<span class="sig-arg">self</span>,
        <span class="sig-arg">source</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Return the shortest path distance between source node and all other 
  nodes using Dijkstra's algorithm.</p>
  <dl class="fields">
    <dt>Parameters:</dt>
    <dd><ul class="nomargin-top">
        <li><strong class="pname"><code>source</code></strong> (node) - Node from which to start the search.</li>
    </ul></dd>
    <dt>Returns: tuple</dt>
        <dd>A tuple containing two dictionaries, each keyed by target nodes.
          <ol start="1">
            <li>
              Shortest path spanning tree
            </li>
            <li>
              Shortest distance from given source to each target node
            </li>
          </ol>
          <p>Inaccessible target nodes do not appear in either 
          dictionary.</p></dd>
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        All weights must be nonnegative.
      </p>
</div></td></tr></table>
</div>
<a name="topological_sorting"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">topological_sorting</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Topological sorting.</p>
  <dl class="fields">
    <dt>Returns: list</dt>
        <dd>Topological sorting for the graph.</dd>
  </dl>
<div class="fields">      <p><strong>Attention:</strong>
        Topological sorting is meaningful only for directed acyclic graphs.
      </p>
</div></td></tr></table>
</div>
<a name="find_cycle"></a>
<div>
<table class="details" border="1" cellpadding="3"
       cellspacing="0" width="100%" bgcolor="white">
<tr><td>
  <table width="100%" cellpadding="0" cellspacing="0" border="0">
  <tr valign="top"><td>
  <h3 class="epydoc"><span class="sig"><span class="sig-name">find_cycle</span>(<span class="sig-arg">self</span>)</span>
  </h3>
  </td><td align="right" valign="top"
    >&nbsp;
    </td>
  </tr></table>
  
  <p>Find a cycle in the digraph.</p>
  <p>This function will return a list of nodes which form a cycle in the 
  graph or an empty list if no cycle exists.</p>
  <dl class="fields">
    <dt>Returns: list</dt>
        <dd>List of nodes.</dd>
  </dl>
</td></tr></table>
</div>
<br />
<!-- ==================== NAVIGATION BAR ==================== -->
<table class="navbar" border="0" width="100%" cellpadding="0"
       bgcolor="#a0c0ff" cellspacing="0">
  <tr valign="middle">
  <!-- Home link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="graph-module.html">Home</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Tree link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="module-tree.html">Trees</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Index link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="identifier-index.html">Indices</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Help link -->
      <th>&nbsp;&nbsp;&nbsp;<a
        href="help.html">Help</a>&nbsp;&nbsp;&nbsp;</th>

  <!-- Project homepage -->
      <th class="navbar" align="right" width="100%">
        <table border="0" cellpadding="0" cellspacing="0">
          <tr><th class="navbar" align="center"
            ><a class="navbar" target="_top" href="http://code.google.com/p/python-graph/">python-graph</a></th>
          </tr></table></th>
  </tr>
</table>
<table border="0" cellpadding="0" cellspacing="0" width="100%%">
  <tr>
    <td align="left" class="footer">
    Generated by Epydoc 3.0.1 on Sun May  3 19:28:09 2009
    </td>
    <td align="right" class="footer">
      <a target="mainFrame" href="http://epydoc.sourceforge.net"
        >http://epydoc.sourceforge.net</a>
    </td>
  </tr>
</table>

<script type="text/javascript">
  <!--
  // Private objects are initially displayed (because if
  // javascript is turned off then we want them to be
  // visible); but by default, we want to hide them.  So hide
  // them unless we have a cookie that says to show them.
  checkCookie();
  // -->
</script>
</body>
</html>
